package dynamic;

public class CoinsGame
{
  public int coins(int[] A)
  {
      int n=A.length;
      int[][] sum=new int[n][n];
      int[][] dp=new int[n][n];
        
      for(int i=n-1;i>=0;i--)
          for(int j=i;j<n;j++)
              sum[i][j]=A[j]+(i==j?0:sum[i][j-1]);
        
      for(int i=n-1;i>=0;i--)
          for(int j=i;j<n;j++)
          {
              if(i==j)
                  dp[i][j]=A[i];
              else
                  dp[i][j]=sum[i][j]-Math.min(dp[i+1][j], dp[i][j-1]);
          }
      return dp[0][n-1];
  }
  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
